Search results for "discrete [space-time]"
showing 10 items of 2035 documents
Ambainis-Freivalds’ Algorithm for Measure-Once Automata
2001
An algorithm given by Ambainis and Freivalds [1] constructs a quantum finite automaton (QFA) with O(log p) states recognizing the language Lp = {ai| i is divisible by p} with probability 1 - Ɛ , for any Ɛ > 0 and arbitrary prime p. In [4] we gave examples showing that the algorithm is applicable also to quantum automata of very limited size. However, the Ambainis-Freivalds algoritm is tailored to constructing a measure-many QFA (defined by Kondacs andWatrous [2]), which cannot be implemented on existing quantum computers. In this paper we modify the algorithm to construct a measure-once QFA of Moore and Crutchfield [3] and give examples of parameters for this automaton. We show for the lang…
Tentative Recommendation on Terminology and Definitions in Respiratory Physiology: Résumé of the Isott Consensus Session 1992
1994
1 The use of small letters for the symbols “p” (partial pressure), “s” (saturation) and “c” (concentration) (e.g. pO2, sO2, cO2) follows recommendations of the IFCC and IUPAC [4]. This supports the use of contemporary word processing systems and mostly eliminates the need to use subscripts (except for chemical valencies: e.g. O2, CO2, H2CO3 etc.). The potential risk of misinterpretations and double meanings is reduced also (e.g. “cO2” [oxygen concentration] v.s. “CO2” [carbon dioxide] and “sO2” [oxygen saturation] v.s. “sO2” [sulfur dioxide]). 2 The symbol shall include the site of measurement or description, e.g. paO2 (arterial O2 partial pressure), svO2 (mixed venous oxygen saturation), o…
Maximal function estimates and self-improvement results for Poincaré inequalities
2018
Our main result is an estimate for a sharp maximal function, which implies a Keith–Zhong type self-improvement property of Poincaré inequalities related to differentiable structures on metric measure spaces. As an application, we give structure independent representation for Sobolev norms and universality results for Sobolev spaces. peerReviewed
Three-page encoding and complexity theory for spatial graphs
2004
We construct a series of finitely presented semigroups. The centers of these semigroups encode uniquely up to rigid ambient isotopy in 3-space all non-oriented spatial graphs. This encoding is obtained by using three-page embeddings of graphs into the product of the line with the cone on three points. By exploiting three-page embeddings we introduce the notion of the three-page complexity for spatial graphs. This complexity satisfies the properties of finiteness and additivity under natural operations.
Characterization and Extraction of Irredundant Tandem Motifs
2012
We address the problem of extracting pairs of subwords (m1,m2) from a text string s of length n, such that, given also an integer constant d in input, m1 and m2 occur in tandem within a maximum distance of d symbols in s. The main effort of this work is to eliminate the possible redundancy from the candidate set of the so found tandem motifs. To this aim, we first introduce the concept of maximality, characterized by four specific conditions, that we show to be not deducible by the corresponding notion of maximality already defined for "simple" (i.e., non tandem) motifs. Then, we further eliminate the remaining redundancy by defining the concept of irredundancy for tandem motifs. We prove t…
On the empirical spectral distribution for certain models related to sample covariance matrices with different correlations
2021
Given [Formula: see text], we study two classes of large random matrices of the form [Formula: see text] where for every [Formula: see text], [Formula: see text] are iid copies of a random variable [Formula: see text], [Formula: see text], [Formula: see text] are two (not necessarily independent) sets of independent random vectors having different covariance matrices and generating well concentrated bilinear forms. We consider two main asymptotic regimes as [Formula: see text]: a standard one, where [Formula: see text], and a slightly modified one, where [Formula: see text] and [Formula: see text] while [Formula: see text] for some [Formula: see text]. Assuming that vectors [Formula: see t…
Two-view “cylindrical decomposition” of binary images
2001
This paper describes the discrete cylindrical algebraic decomposition (DCAD) construction along two orthogonal views of binary images. The combination of two information is used to avoid ambiguities for image recognition purposes. This algorithm associates an object connectivity graph to each connected component, allowing a complete description of the structuring information. Moreover, an easy and compact representation of the scene is achieved by using strings in a five letter alphabet. Examples on complex digital images are also provided. © 2001 Elsevier Science Inc.
Ahlfors-regular distances on the Heisenberg group without biLipschitz pieces
2015
We show that the Heisenberg group is not minimal in looking down. This answers Problem 11.15 in `Fractured fractals and broken dreams' by David and Semmes, or equivalently, Question 22 and hence also Question 24 in `Thirty-three yes or no questions about mappings, measures, and metrics' by Heinonen and Semmes. The non-minimality of the Heisenberg group is shown by giving an example of an Ahlfors $4$-regular metric space $X$ having big pieces of itself such that no Lipschitz map from a subset of $X$ to the Heisenberg group has image with positive measure, and by providing a Lipschitz map from the Heisenberg group to the space $X$ having as image the whole $X$. As part of proving the above re…
Norm, essential norm and weak compactness of weighted composition operators between dual Banach spaces of analytic functions
2017
Abstract In this paper we estimate the norm and the essential norm of weighted composition operators from a large class of – non-necessarily reflexive – Banach spaces of analytic functions on the open unit disk into weighted type Banach spaces of analytic functions and Bloch type spaces. We also show the equivalence of compactness and weak compactness of weighted composition operators from these weighted type spaces into a class of Banach spaces of analytic functions, that includes a large family of conformally invariant spaces like BMOA and analytic Besov spaces.
The Average State Complexity of the Star of a Finite Set of Words Is Linear
2008
We prove that, for the uniform distribution over all sets Xof m(that is a fixed integer) non-empty words whose sum of lengths is n, $\mathcal{D}_X$, one of the usual deterministic automata recognizing X*, has on average $\mathcal{O}(n)$ states and that the average state complexity of X*is i¾?(n). We also show that the average time complexity of the computation of the automaton $\mathcal{D}_X$ is $\mathcal{O}(n\log n)$, when the alphabet is of size at least three.